/******************************************************************************
 *  _____     _____
 *  \  __\    \  __\
 *   \ \_\\    \ \_\\
 *    \  __\SS  \  __\roject
 *     \_\       \_\
 *
 * Mateusz Maciąg, Rafał Urbański
 * Komputerowe Systemy Sterowania
 *****************************************************************************/

#ifndef POLYNOMIAL_H
#define POLYNOMIAL_H

#include <iosfwd>
#include <vector>
#include <iterator>

// Przestrzeń nazw
namespace RafMat
{
namespace SimEngine
{

/** Klasa reprezentująca wielomian.

  Reprezentowany wielomian jest funkcją o parametrach rzeczywistych (typ double).
  Wyliczane wartości są również typu rzeczywistego, choć łatwo można rozszerzyć obliczanie
  wartości liczb zespolonych.

  Wielomian, oprócz przechowywania parametrów, umożliwia wykonywanie podstawowych działań
  arytmetycznych (dodawanie, odejmowanie, mnożenie, negacja).

  \todo Nie wszystkie zadeklarowane metody zostały zaimplementowane, głównie te,
  które prawie na pewno się nie przydadzą w projekcie. Jednakowoż można uzupełnić
  ich implementacje w chwili wolnej od spania.
*/
class Polynomial
{
    // Konfiguracja
    static const double COMPARISON_TOLERANCE;
    static const double TRIM_TOLERANCE;

    //
    // Deklaracje przyjaźni
    //
    /**
        Wyrzuca wielomian na wyjście w postaci wektora współczynników:
        [ a0 a1 a2 ... aN ].

        \code
        Polynomial testPoly(5);
        std::cout << testPoly; // Wyświetli [ 5 ]
        \endcode

        \param [in] os strumień docelowy
        \param [in] polyRhs prawa strona dodawania
        \return suma wielomianów
    */
    friend std::ostream& operator << (std::ostream& os, const Polynomial &poly);
    //friend std::istream& operator >> (std::istream& os, const Polynomial &poly);

    /**
        Dodawanie wielomianów
        Dodaje dwa wielomiany i zwraca sumę jako niezależną instancję.
        Konstruktor konwertujący pozwala na dodawanie wielomianów oraz zmiennych double.

        \todo Zoptymalizować dodawanie i odejmowanie wielomianów. Na chwilę obecną wykonywane są podwójne kopie
        - raz przy tworzeniu wielomianu, drugi raz przy zwracaniu przez wartość.

        \param [in] polyLhs lewa strona dodawania
        \param [in] polyRhs prawa strona dodawania
        \return Suma wielomianów.
    */
    friend Polynomial operator + (const Polynomial &polyLhs, const Polynomial &polyRhs);

    /**
        Odejmuje dwa wielomiany i zwraca różnicę jako niezależną instancję.
        Konstruktor konwertujący pozwala na dodawanie wielomianów oraz zmiennych double.

        \param [in] polyLhs lewa strona odejmowania
        \param [in] polyRhs prawa strona odejmowania
        \return Różnica wielomianów.
    */
    friend Polynomial operator - (const Polynomial &polyLhs, const Polynomial &polyRhs);

    friend Polynomial operator * (const Polynomial &polyLhs, const Polynomial &polyRhs);

    friend Polynomial operator * (double c, const Polynomial &polyRhs);
    friend Polynomial operator * (const Polynomial &polyLhs, double c);
    friend Polynomial operator / (const Polynomial &polyLhs, const Polynomial &polyRhs);
    friend Polynomial operator / (const Polynomial &polyLhs, double c);   

    // Przesuwanie współczynników
    friend Polynomial operator << (const Polynomial &poly, unsigned int i);
    friend Polynomial operator >> (const Polynomial &poly, unsigned int i);

    //
    // Operatory porównania
    //

    friend bool operator == (const Polynomial &polyLhs, const Polynomial &polyRhs);
    friend bool operator != (const Polynomial &polyLhs, const Polynomial &polyRhs);

public:

    //
    // Typy danych
    //

    typedef std::vector<double> PolyType;

    /**
        Wykonuje mnożenie dwóch wielomianów.

        Mnożenie odpowiada splotowi współczynników.

        \param [in] polyLhs lewa strona mnożenia
        \param [in] polyRhs prawa strona mnożenia
        \param [out] out Wynik mnożenia zwracany przez referencję
    */
    static void multiply(const Polynomial &polyLhs, const Polynomial &polyRhs, Polynomial &out);

    /**
        Wykonuje dzielenie dwóch wielomianów.

        Funkcja zwraca tylko iloraz, reszta z dzielenia, o ile jest niezerowa, jest ignorowana.

        \param [in] polyLhs lewa strona dzielenia (dzielna)
        \param [in] polyRhs prawa strona dzielenia (dzielnik)
        \param [out] out Wynik dzielenia zwracany przez referencję
    */
    static void divide(const Polynomial &polyLhs, const Polynomial &polyRhs,
                       Polynomial &out);

    /**
        Wykonuje dzielenie dwóch wielomianów.

        Funkcja zwraca wynik dzielenia i resztę dzieenia.

        \param [in] polyLhs lewa strona dzielenia (dzielna)
        \param [in] polyRhs prawa strona dzielenia (dzielnik)
        \param [out] quotient Wynik dzielenia zwracany przez referencję
        \param [out] reminder Reszta dzielenia zwracana przez referencję
    */
    static void divide(const Polynomial &polyLhs, const Polynomial &polyRhs,
                       Polynomial &quotient, Polynomial &reminder);


    static void gcd(const Polynomial &p, const Polynomial &q, Polynomial &g);

    /**
        Konstruktor domyślny tworzący wielomian 'zerowy'.
        Tworzy wielomian stały. Domyślnie jest to y = 0.
        Konstruktor umożliwia konwersję automatyczną z typu double.

        \param [in] c wyraz wolny wielomianu stałego.
    */
    Polynomial(double c = 0);

    /**
        Konstruktor inicjalizujący wielomian dowolnego stopnia z
        domyślną wartością współczynników.

        Uwaga: dla \c initVal = 0 zostanie wielomian nadal będzie miał
        rząd \c degree.

        \param [in] degree Stopień wielomianu.
        \param [in] initVal Domyślne współczynniki wielomianu.
    */
    Polynomial(int degree, double initVal);

    /**
        Tworzy odrębną kopię wielomianu.
        Konstruktor ten nie jest konieczny, może być generowany automatycznie.
        Zastosowany w celu śledzenia liczby kopiowań w trakcie stosowania
        operatorów.

        \param [in] c wielomian do skopiowania.
    */
    Polynomial(const Polynomial &c);

    /**
        Konstruktor tworzący wielomian na podstawie współczynników.
        Tworzy wielomian na podstawie wektora współczynników.
        Współczynniki zawsze liczone są od najniższej potęgi, tzn. element zerowy
        wektora jest wyrazem wolnym wielomianu.

        y = a0 + a1*x + a2*x^2 + ... + an*x^n

        \param [in] coeefs - wektor standardowy współczynników wielomianu.
    */
    explicit Polynomial(const PolyType &coeffs);

    /**
        Szablon konstruktora tworzący wielomian na podstawie iteratorów.
    */
    template < typename _InIt > Polynomial(_InIt first, _InIt last, bool dummy)
    {
        (void) dummy;

        std::copy(first, last, std::back_inserter(m_coeffs));
    }

    /**
        Wyznacza wartość wielomianu dla danego argumentu
        Funkcja wylicza wartość wielomianu w punkcie \c arg. W szczególności
        dla arg = 0 zwracany jest wyraz wolny.

        Schemat Hornera - źródło wikipedia.pl:
        \code
        coefficients := [-19, 7, -4, 6] # list coefficients of all x^0..x^n in order
        x := 3
        accumulator := 0
        for i in length(coefficients) downto 1 do
            # Assumes 1-based indexing for arrays
            accumulator := ( accumulator * x ) + coefficients[i]
        done
        # accumulator now has the answer
        \endcode
    */
    double evaluate(double arg) const;

    /**
        Zwraca stopień wielomianu.
    */
    unsigned degree() const { return m_coeffs.size()-1; }

    /**
        Zwraca normę wielomianu.

        Współczynniki wielomianu traktuje się jako pojedynczy wektor i oblicza się na jego
        podstawie normę. Aktualnie jest to norma L1.
    */
    double norm() const;

    void limitCoeffs(double limitVal);

    /**
        Wymusza rząd wielomianu dodając zerowe współczynniki lub likwidując
        wyższe stopnie niż podany .
    */
    void forceDegree(unsigned degree) { m_coeffs.resize(degree + 1); }

    /**
        Obcina zerowe współczynniki przy najwyższych potęgach.
    */
    Polynomial trim() const;

    /**
        Obcina określoną liczbę współczynników przy najwyższych potęgach.
    */
    //Polynomial trim(int tcount) const;

    /**
        Zwraca liczbę zerowych współczynników, które niczego nie wznoszą do postaci wielomianu
        (sztucznie zawyżają rząd).
    */
    int dummyZeros() const;

    /**
        Odwraca współczynniki.

        Z wielomianu a0 + a1*x + ... + an*x^n robi wielomian an + an-1 * x + ... + a0 * x^n
    */
    Polynomial reverse() const;

    /**
        Zwróć współczynniki jako wektor.
        Wykonywana jest kopia wektora.
    */
    PolyType getCoeffs() const { return m_coeffs; }

    /**
        Zwraca współczynniki jako wektor.
        Zwracana jest referencja do obiektu. Pozwala na modyfikację współczynników.
    */
    PolyType& getCoeffs() { return m_coeffs; }

    /**
        Zwraca współczynnik przy najwyższej potędze.
    */
    double high() const { return m_coeffs.back(); }

    /**
        Przypisuje wartość współczynnikowi.
    */
    void setCoeff(PolyType::size_type index, double val) { if(degree() < index) m_coeffs.resize(index+1); m_coeffs[index] = val; }

    /** Zwraca jednomian na podstawie nr współczynnika */
    Polynomial getMonomial(PolyType::size_type index) const { return Polynomial(m_coeffs[index]) >> index; }

    //
    // Iteratory
    //

    /** Iterator wskazujący na wyraz wolny wielomianu. */
    PolyType::iterator begin() { return m_coeffs.begin(); }

    /** Iterator wskazujący na wyraz przy najwyższej potędze. */
    PolyType::iterator end() { return m_coeffs.end(); }

    /** Iterator wskazujący na wyraz wolny wielomianu (wersja const). */
    PolyType::const_iterator begin() const { return m_coeffs.begin(); }

    /** Iterator wskazujący na wyraz przy najwyższej potędze (wersja const). */
    PolyType::const_iterator end() const { return m_coeffs.end(); }


    /** Odpowiednik begin(), iterator odwrotny. */
    PolyType::reverse_iterator rbegin() { return m_coeffs.rbegin(); }

    /** Odpowiednik end(), iterator odwrotny. */
    PolyType::reverse_iterator rend() { return m_coeffs.rend(); }

    /** Odpowiednik begin() const, iterator odwrotny. */
    PolyType::const_reverse_iterator rbegin() const { return m_coeffs.rbegin(); }

    /** Odpowiednik end() const, iterator odwrotny. */
    PolyType::const_reverse_iterator rend() const { return m_coeffs.rend(); }


    //
    // Przeciążone operatory
    //

    /**
        Wywołanie funckji wielomianowej dla danego argumentu.

        Przeciążenie operatora funkcyjnego pozwala na wypisanie wartości wielomianu
        dla danej liczby w tradycyjny sposób: y = W(5) zamiast y = W.evaluate(5).

        \param [in] arg Argument funkcji wielomianowej.
        \return Wartość funkcji.

        \see evaluate(double)
    */
    double operator () (double arg) const { return evaluate(arg); }

    /**
        Operator tablicowy dla współczynników wielomianu (tylko do odczytu).

        \param [in] coeffIndex Indeks współczynnika wielomianu (0 - wyraz wolny).
        \return Wartość współczynnika.
    */
    double operator [] (int coeffIndex) const { return m_coeffs[coeffIndex]; }

    /**
        Operator tablicowy dla współczynników wielomianu (zapis i odczyt).

        \param [in] coeffIndex Indeks współczynnika wielomianu (0 - wyraz wolny).
        \return Wartość współczynnika (modyfikowalna).
    */
    double& operator [] (int coeffIndex) { return m_coeffs[coeffIndex]; }

    /** Przypisanie z dodawaniem.

        Dodaje do bierzącej instancji inny wielomian. Umożliwia zapis typu:

        \code
        Polynomian a, b;
        a += b + 5;
        \endcode

        \param [in] polyRhs prawa strona przypisania
        \return Referencja do bierzącego obiektu (zmienionego).
    */
    Polynomial& operator += (const Polynomial &polyRhs);

    /** Przypisanie z odejmowaniem. */
    Polynomial& operator -= (const Polynomial &polyRhs);

    /** Przypisanie z mnożeniem. */
    Polynomial& operator *= (double cRhs);

    /** Przypisanie z mnożeniem. */
    Polynomial& operator *= (const Polynomial &polyRhs);

    /** Przypisanie z dzieleniem. */
    Polynomial& operator /= (double cRhs);

    /** Przypisanie z dzieleniem. */
    Polynomial& operator /= (const Polynomial &polyRhs);

    /** Unarny plus. */
    Polynomial operator + () const { return *this; }

    /** Unarny minus.
        Zwraca wartość przeciwną wielomianu tzn. dla wielomianu
        [a0 ... aN] zwraca [-a0 ... -aN].

        Nieoptymalne pod względem kopiowania.

        \return Wielomian przeciwny.
    */
    Polynomial operator - () const;

    // Operatory porównania

private:

    void trimSelf();

    PolyType m_coeffs;   ///< Współczynniki wielomianu
};

}   // SimEngine namespace
}   // RafMat namespace

#endif // POLYNOMIAL_H
